package com.jeff.learn.recursion;

/**
 * 递归实现插入排序
 *
 * @author yaojianfeng
 */
public class RecursionInsertSort {
    public static void main(String[] args) {
        int[] arr = {9, 5, 2, 8, 6, 3, 1, 7, 4};
//        insertSort2(arr, 0);
        insertSort(arr, arr.length);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    /**
     * 递归实现插入排序 -头递归
     *
     * @param arr 数组
     * @param length   待排序的数组长度
     */
    public static void insertSort(int[] arr, int length) {
        // 如果数组长度小于等于1，则无需排序，直接返回
        if (length <= 1) {
            return;
        }
        // 递归调用insertSort 将问题简化至只有两个元素的排序
        insertSort(arr, length - 1);
        //待插入元素
        int temp = arr[length - 1];
        // sortIndex初始值 指向已排序数组的最大索引
        int sortIndex = length - 2;
        // 将比temp大的元素后移一位，为temp腾出插入位置
        while (sortIndex >= 0 && arr[sortIndex] > temp) {
            arr[sortIndex + 1] = arr[sortIndex];
            // 继续向前寻找插入位置
            sortIndex--;
        }
        // 插入temp到合适的位置，完成一轮排序
        arr[sortIndex + 1] = temp;
    }

    /**
     * 递归实现插入排序 -尾递归优化
     *
     * @param arr         数组
     * @param sortedCount 已排序的元素个数
     */
    public static void insertSort2(int[] arr, int sortedCount) {

        //递归终止条件 当已排序的元素个数等于数组长度时，排序结束
        if (sortedCount == arr.length) {
            return;
        }
        // 声明待插入元素
        int temp = arr[sortedCount];
        //声明被比较元素的初始索引
        int compareIndex = sortedCount - 1;
        // 寻找插入位置 - 向前寻找比temp小的元素，并将其后移一位，为temp腾出插入位置
        while (compareIndex >= 0 && arr[compareIndex] > temp) {
            arr[compareIndex + 1] = arr[compareIndex];
            compareIndex--;
        }
        // 插入temp到合适的位置
        arr[compareIndex + 1] = temp;

        // 递归调用 已排序个数+1
        insertSort2(arr, sortedCount + 1);
    }

}
